package com.es.segment;

/**
 * leetcode 303
 *
 * @author 二十
 * @since 2022/1/19 8:37 上午
 */
public class SegmentTree<E> extends AbstractSegmentTree<E> {

    private E[] data;

    private E[] tree;

    private Merge<E> merge;

    public SegmentTree(E[] array, Merge<E> merge) {
        this.merge = merge;
        tree = (E[]) new Object[4 * array.length];
        data = (E[]) new Object[array.length];
        for (int i = 0; i < data.length; i++) {
            data[i] = array[i];
        }
        buildSegmentTree(0, 0, data.length - 1);
    }

    private void buildSegmentTree(int index, int l, int r) {
        //此时代表是根节点
        if (l == r) {
            tree[index] = data[l];
            return;
        }
        /*
        接下来就不是根节点的情况了：
        这个时候需要递归去创建左右子树
         */
        int leftIndex = leftChild(index);
        int rightIndex = rightChild(index);
        int mid = l + (r - l) / 2;
        buildSegmentTree(leftIndex, l, mid);
        buildSegmentTree(rightIndex, mid + 1, r);
        tree[index] = merge.merge(tree[leftIndex], tree[rightIndex]);
    }


    @Override
    public E get(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("参数错误！");
        }
        return data[index];
    }

    @Override
    public int getSize() {
        return data.length;
    }

    @Override
    public int leftChild(int index) {
        return 2 * index + 1;
    }

    @Override
    public int rightChild(int index) {
        return 2 * index + 2;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < tree.length; i++) {
            if (tree[i] != null) {
                sb.append(tree[i]);
            } else {
                sb.append("null");
            }
            if (i != tree.length - 1) {
                sb.append(",");
            }
        }
        return sb.append("]").toString();
    }

    public interface Merge<E> {
        E merge(E a, E b);
    }

    @Override
    public E query(int queryL, int queryR) {
        if (queryL < 0 || queryL >= data.length || queryR < 0 || queryR >= data.length || queryL > queryR) {
            throw new IllegalArgumentException("index is illegal!");
        }
        return query(0, 0, data.length - 1, queryL, queryR);
    }

    private E query(int index, int start, int end, int queryL, int queryR) {

        if (start == queryL && end == queryR) {
            return tree[index];
        }
        int mid = start + (end - start) / 2;
        int left = leftChild(index);
        int right = rightChild(index);

        if (queryR <= mid) {
            return query(left, start, mid, queryL, queryR);
        }
        if (queryL >= mid + 1) {
            return query(right, mid + 1, end, queryL, queryR);
        }
        return merge.merge(query(left, start, mid, queryL, mid), query(right, mid + 1, end, mid + 1, queryR));
    }

    @Override
    public void set(int index, E e) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException("error");
        }
        //修改数组
        data[index] = e;
        //修改线段树
        set(0, 0, data.length - 1, index, e);
    }

    /**
     * @param index 数组中要更改的索引位置
     * @param start 修改的范围开始
     * @param end   修改的范围结束
     * @param idx   开始修改的树的索引
     * @param e     修改后的值
     */
    private void set(int idx, int start, int end, int index, E e) {

        if (start == end) {
            tree[idx] = e;
            return;
        }
        int mid = start + (end - start) / 2;
        int left = leftChild(idx);
        int right = rightChild(idx);
        if (index >= mid + 1) {
            set(right, mid + 1, end, index, e);
        } else if (index <= mid) {
            set(left, start, mid, index, e);
        }
        tree[idx] = merge.merge(tree[left], tree[right]);
    }
}
